package Algorithm.dynamicProgramming.swordOffer;

/**
 * 剑指 Offer 47. 礼物的最大价值 https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/
 * 题目简述：m*n的棋盘上每个格子都有一个价值大于0的礼物，从左上角出发，每次只能向右或向下走一格，问走到右下角能获得礼物的最大价值
 */
public class MaxValue {

    /**
     * 动态规划
     * 1. 定义dp: dp[i][j]为到达坐标（i,j）的格子能获取到礼物的最大价值总和。左上角起点格子为（0,0）
     * 2. 状态转移公式：只能由上方或左边格子走来，故dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + grid[i][j]
     *                 注意处理第一行和第一列的特殊情况
     * 3. 初始化：dp[0][0] = grid[0][0]
     * 4. 遍历方式：从上到下逐行遍历
     */
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 0;i < m;i++) {
            for (int j = 0;j < n;j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0) dp[i][j] = dp[i][j-1] + grid[i][j];
                else if (j == 0) dp[i][j] = dp[i-1][j] + grid[i][j];
                else dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }

    /**
     * 优化：每一层dp[i][j]只与当前层左边和正上方的数据有关，故可使用滚动数组进行优化
     */
    public int maxValue2(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        dp[0] = grid[0][0];
        for (int i = 0;i < m;i++) {
            for (int j = 0;j < n;j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0) dp[j] = dp[j-1] + grid[i][j];
                else if (j == 0) dp[j] = dp[j] + grid[i][j];
                else dp[j] = Math.max(dp[j-1], dp[j]) + grid[i][j];
            }
        }
        return dp[n-1];
    }
}
